The present invention pertains to the field of wireless communication technology. More specifically, the present invention pertains to decoding signals received by a receiver in a wireless communication system.
Wireless telephony has become a widely available mode of communication in modem society. Variable rate communication systems, such as Code Division Multiple Access (CDMA) spread spectrum systems, are among the most commonly deployed wireless technology. Variable rate communication systems transmit data in units called data frames.
CDMA utilizes digital encoding for every telephone call or data transmission in order to provide privacy and security. Unique codes are assigned to every communication, which distinguish it from the multitude of calls simultaneously transmitted over the same broadcast spectrum. Users share time and frequency allocations and are channelized by unique assigned codes. The signals are separated at the receiver in a known manner so that the receiver accepts only signals from the desired channel.
Some CDMA spread spectrum systems use a form of direct sequence in which, in essence, a communication waveform is modified by a pseudonoise binary sequence in the transmitter. A second modification by a replica of the pseudonoise binary sequence occurs in the receiver to recover the original signal. Generally, within a CDMA environment with a large number of users on the system, a high level of channel noise is usually present. In particular, each user is a source of noise to every other user on the same system. Undesired signals also contribute to the noise. Noise and interference, being uncorrelated with the pseudonoise binary sequence, add an element to the signal that needs to be considered when recovering the original signal.
Convolutional codes are known in the art and are used by the transmitter to encode a stream of binary digits. Typically, a convolutional encoder consists of a N-stage shift register and modulo-2 adders. Each digit of the digit stream is input into the shift register, and the convolutional code generates output digits that are an encoded version of the each input digit. For example, if the coding rate is xc2xd, two output digits are generated for each input digit. A convolutional code is often represented in a known fashion using a trellis that shows the coded output for any possible sequence of input digits.
At the receiver, various techniques are known in the art for decoding a digital stream encoded using convolutional codes. The coding polynomial used in the convolutional code utilized by the transmitter is specified for the receiver, and so the receiver is able to decode the transmitted signal to determine expected values. However, due to the introduction of noise and interference during transmission, the received signal is likely to be different from the transmitted signal. A Viterbi decoder provides a well-known method to correct for errors introduced by noise and interference to determine decoded values based on the received signal. In essence, a Viterbi decoder determines the path through the convolutional code trellis that results in the sequence of digits that agrees most with the received sequence.
Viterbi decoders, their function and implementation are well-known in the art. Expected values for each data frame are determined using the same convolutional code used by the transmitter. The Viterbi decoder computes a metric (such as a Hamming distance or the like) for each branch that feeds into a node (xe2x80x9cstatexe2x80x9d) in the convolutional code trellis. The metrics are computed by comparing the received signal and the expected values. The metric for each state is stored in a random access memory unit (e.g., a metric memory).
The metrics for each state are accumulated for each stage of the Viterbi decoder process by adding the state metrics of the corresponding state in the previous stage to the corresponding branch metric (a stage is one cycle through all the states). Due to the nature of the Viterbi decoder trellis and the necessity for metrics from the preceding stage to compute new state metrics, the metric memory cannot be overwritten during the Viterbi decoder process until all state metrics are evaluated for a stage.
One prior art implementation of a metric memory involves using two memory arrays, each array having the same number of locations as there are number of states. One of the arrays is used to store state metrics for the originating stage, and the other array is used to store the metrics for the next stage as they are being calculated. After all of the new state metrics are calculated for a stage, the values in the second array are then copied to the first array before the process is repeated for the next stage. However, this prior art approach is problematic because it requires two full-size arrays, occupying valuable physical space inside the receiver. In addition, this arrangement results in a large number of read and write transactions in order to copy the values from one array to the other. Thus, this approach also consumes processing power, and so larger, more complex and consequently more expensive processors are required if an acceptable performance level is to be maintained. Also, this approach consumes battery power, and so larger and heavier batteries are needed to avoid frequent charging. Consumer preferences are for receivers to be as small, light and inexpensive as possible, and the need for large memory spaces is contrary to these preferences.
Another prior art approach that reduces the number of read and write transactions uses two xe2x80x9cping-pongxe2x80x9d memories that work in tandem. For one stage, the first array is used to read current state metrics and the second array is used to write state metrics for the next stage; for the next stage, the functions are reversed. However, this approach is still problematic because it requires two full-size arrays, occupying valuable physical space inside the receiver. Thus, this prior art approach shares the same problems as the approach described above with regard to size, weight and expense.
Other prior art approaches have attempted to solve the problems associated with memory size by writing two metrics per location in order to reduce memory size by one-half. One problem with these types of approaches is that, because two values are stored in the same location, both values are read when only one value is needed. For a single port memory, only one value can be read at a time, and so one processor cycle is required to read the first value, and another processor cycle is needed for the second value. Additional control logic is required in order to determine which of the two values is needed and to isolate that value. A dual port memory can be used to increase the speed at which the two values are read; however, a problem still exists with regard to determining which value is needed and isolating that value. Thus, these approaches can require complicated control logic, additional data lines, and additional address logic. These approaches therefore also require additional processing power and battery power, and so also share the same problems as the approaches described above with regard to size, weight and expense.
Accordingly, what is needed is an apparatus that efficiently and quickly stores and retrieves state metrics in order to reduce memory size. What is also needed is an apparatus that addresses the above needs and minimizes the associated address logic. In addition, what is needed is an apparatus that addresses the above needs and minimizes consumption of space, processing power, and battery power in a receiver. The present invention provides a novel solution to the above needs.
These and other objects and advantages of the present invention will become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.
The present invention provides an apparatus and method thereof that efficiently and quickly store and retrieve state metrics in order to reduce memory size. The present invention also provides an apparatus and method thereof that minimize the associated address logic. In addition, the present invention provides an apparatus and method thereof that minimize consumption of space, processing power, and battery power in a receiver.
The present embodiment of the present invention pertains to an apparatus and method thereof for implementing a Viterbi decoder. In a preferred embodiment, the apparatus is disposed within a receiver used in a communication system, in particular a communication system that uses code division multiple access (CDMA) spread spectrum type communication signals.
In the present embodiment of the present invention, the apparatus includes a bus and a branch metric generator unit coupled to the bus. The branch metric generator unit generates metrics by measuring a difference between an encoded data bit and an expected data bit calculated using a convolutional code. A memory unit is also coupled to the bus. The memory unit includes a first register and a second register for storing the metrics. A parity bit is used to indicate a register for storing the metrics. In a first stage of the Viterbi decoder, a metric for a first state is stored at a first address in the first register and a metric for a second state is stored at a second address in the second register. The first state and the second state each branch to a third state and a fourth state in a trellis code of the Viterbi decoder.
In one embodiment, in a second stage of the Viterbi decoder, a metric for the third state is stored at the first address in the first register and a metric for the fourth state is stored at a second address in the second register. A parity bit is used to indicate a register for storing the metric for the third state and the metric for the fourth state.
In one embodiment, a N-bit counter is adapted to generate a sequence of N binary bits. The sequence of N binary bits is used to generate the first address and the second address in the memory unit. In this embodiment, the sequence of N binary bits is also used generate the parity value.